#include "binarySearchTree.h"
#include "doubleLinkListQueue.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

/* 状态码 */
enum STATUS_CODE
{
    ON_SUCCESS,
    MALLOC_ERROR,
    NULL_PTR,
    INVALID_ACCESS,
};

/* 创建二叉搜索树的前置声明 */
static BinarySearchTreeNode *createBinarySearchTreeNode(ELEMENTTYPE data, BinarySearchTreeNode *parent);

/* 结点的度为2 */
static int BinarySearchTreeNodeTwoChildrens(BinarySearchTreeNode *node);

/* 结点的度为1 */
static int BinarySearchTreeNodeOneChildrens(BinarySearchTreeNode *node);

/* 结点的度为2 */
static int BinarySearchTreeNodeTwoChildrens(BinarySearchTreeNode *node) // ELEMENTTYPE data, BinarySearchTree  * parent
{
    return (node->left != NULL && node->right != NULL);
}

/* 结点的度为1 */
static int BinarySearchTreeNodeOneChildrens(BinarySearchTreeNode *node) //定义输入时错误
{
    return (node->left != NULL && node->right != NULL) || (node->left == NULL && node->right == NULL); //这里后面符改动
}

/* 结点的度为0 (叶子结点) */
static int BinarySearchTreeNodeIsLeaf(BinarySearchTreeNode *node)
{
    return node->left == NULL && node->right == NULL;
}


/* 结点的前驱结点 */
static BinarySearchTreeNode *BinarySearchTreeNodGetPrecursor(BinarySearchTreeNode *node);

/* 结点的后继结点 */
static BinarySearchTreeNode *BinarySearchTreeNodGetSuccessor(BinarySearchTreeNode *node);

/* 树的初始化 */
int BinarySearchTreeInit(BinarySearchTree **pTree, int (*compareFunc)(ELEMENTTYPE arg1, ELEMENTTYPE arg2))
{
    BinarySearchTree *tree = malloc(sizeof(BinarySearchTree) * 1);
    if (tree == NULL)
    {
        return MALLOC_ERROR;
    }

    /* 清除脏数据 */
    memset(tree, 0, sizeof(BinarySearchTree) * 1);

    /* 树的元素为0 */
    tree->size = 0;
    tree->height = 0;
    tree->root = NULL;

    /* 比较器 */
    tree->compareFunc = compareFunc;

    /* 二级指针解引用 */
    *pTree = tree;
    return ON_SUCCESS;
}

//结点的前驱结点
//前驱结点是：当前结点中序遍历（有序）的前面一个结点
static BinarySearchTreeNode  * BinarySearchTreeNodeGetPrecursor(BinarySearchTreeNode * node)
{
    //度为2
    BinarySearchTreeNode * travelNode = NULL;

    //if( BinarySearchTreeNodeHasTwoChildrens(node))
    if(node->left != NULL)
    {
        travelNode = node->left;
        while(travelNode->right != NULL)
        {
            travelNode = travelNode->right;
        }
        return travelNode;
    }

    //程序到这，左子树一定为空
    //找前驱一定是找比他小的
    //只能够往上面（parent->parent->oarent走
    //如果是父节点的右边，则直接返回父节点
    //若果是父节点的左边，则一直往上跑，直到当前结点时父节点的右边
    /* 说明一定度不为2 */

    travelNode = node;
    while(travelNode->parent == NULL && travelNode== travelNode->parent->left)
    {
        travelNode = travelNode->parent;
    }
    return travelNode->parent;
}


//后继结点（中序）
//若果有右子树：node->right->left->left....
//如果没有右子树呢?
static BinarySearchTreeNode  * BinarySearchTreeNodeGetSuccessor(BinarySearchTreeNode * node)
{
    BinarySearchTreeNode * travelNode = NULL;
    if(node->right != NULL)
    {
        travelNode = node->right;
        while(travelNode->left != NULL)
        {
            travelNode = travelNode->left;
        }
        return travelNode;
    }

    //程序到这说明没有右子树，右子树为空。，要往上面走

    travelNode = node;
    while(travelNode->parent == NULL && travelNode== travelNode->parent->right)
    {
        travelNode = travelNode->parent;
    }
    return travelNode->parent;
}


/* 创建二叉搜索树的结点 */
static BinarySearchTreeNode *createBinarySearchTreeNode(ELEMENTTYPE data, BinarySearchTreeNode *parent)
{
    BinarySearchTreeNode *newNode = (BinarySearchTreeNode *)malloc(sizeof(BinarySearchTreeNode) * 1);
    if (newNode == NULL)
    {
        return MALLOC_ERROR; //没有静态前置声明
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    newNode->parent = NULL;
    return newNode;
}

/* 树的插入 */
int binarySearchTreeInsert(BinarySearchTree *pTree, ELEMENTTYPE data)
{
    /* 判空 */
    if (pTree == NULL)
    {
        return NULL_PTR;
    }

    /* 判断是否为空树 */
#if 0
    if (pTree->size == 0)
    {

    }
#else
    if (pTree->root == NULL)
    {
        pTree->root = createBinarySearchTreeNode(data, NULL);
        if (pTree->root == NULL)
        {
            return MALLOC_ERROR;
        }
        return ON_SUCCESS;
    }
#endif

    /* 程序走到这个地方, 一定不是空树 */
    BinarySearchTreeNode *travelNode = pTree->root;

    BinarySearchTreeNode *parentNode = NULL;
    int cmp = 0;
    while (travelNode != NULL)
    {
        parentNode = travelNode;
        /* 比较器 */
        cmp = pTree->compareFunc(data, travelNode->data);
        if (cmp < 0)
        {
            travelNode = travelNode->left;
        }
        else if (cmp == 0)
        {
#if 1
            return ON_SUCCESS;
#else
            travelNode->data = data;
#endif
        }
        else if (cmp > 0)
        {
            travelNode = travelNode->right;
        }
    }
    /* 程序执行到这里 travelNode一定为NULL. */
    BinarySearchTreeNode *newNode = createBinarySearchTreeNode(data, parentNode);
    if (newNode == NULL)
    {
        return MALLOC_ERROR;
    }

    if (cmp < 0)
    {
        parentNode->left = newNode;
    }
    else if (cmp > 0)
    {
        parentNode->right = newNode;
    }

    /* 树的元素个数加一. */
    (pTree->size)++;

    return ON_SUCCESS;
}

/* 前序遍历 */
static int binarySearchTreeInnerPreOrder(BinarySearchTree *pTree, BinarySearchTreeNode * travelNode)
{
    if (travelNode == NULL)
    {
        return ON_SUCCESS;
    }

    /* 根结点 */
    pTree->printFunc(travelNode->data);
    /* 左子树 */
    binarySearchTreePreOrder(travelNode->left);
    /* 右子树 */
    binarySearchTreePreOrder(travelNode->right);

    return ON_SUCCESS;
}

/* 树的前序遍历 */
/* 根结点, 左子树, 右子树 */
int binarySearchTreePreOrder(BinarySearchTree *pTree)
{
    if (pTree == NULL)
    {
        return NULL_PTR;
    }

    return binarySearchTreeInnerPreOrder(pTree, pTree->root);
}

/* 树的中序遍历 */
static int binarySearchTreeInnerInOrder(BinarySearchTree *pTree, BinarySearchTreeNode * travelNode)
{
    if (travelNode == NULL)
    {
        return ON_SUCCESS;
    }

    /* 左子树 */
    binarySearchTreePreOrder(travelNode->left);
    /* 根结点 */
    pTree->printFunc(travelNode->data);
    /* 右子树 */
    binarySearchTreePreOrder(travelNode->right);

    return ON_SUCCESS;
}


/* 树的中序遍历 */
/* 左子树, 根结点, 右子树 */
int binarySearchTreeInOrder(BinarySearchTree *pTree)
{
    if (pTree == NULL)
    {
        return NULL_PTR;
    }

    return binarySearchTreeInnerInOrder(pTree, pTree->root);
}


/* 树的中序遍历 */
static int binarySearchTreeInnerPostOrder(BinarySearchTree *pTree, BinarySearchTreeNode * travelNode)
{
    if (travelNode == NULL)
    {
        return ON_SUCCESS;
    }

    /* 左子树 */
    binarySearchTreePreOrder(travelNode->left);
    /* 右子树 */
    binarySearchTreePreOrder(travelNode->right);
    /* 根结点 */
    pTree->printFunc(travelNode->data);

    return ON_SUCCESS;
}

/* 树的后序遍历 */
/* 左子树, 右子树, 根结点 */
int binarySearchTreePostOrder(BinarySearchTree *pTree)
{
    if (pTree == NULL)
    {
        return NULL_PTR;
    }
    
    return binarySearchTreeInnerPostOrder(pTree, pTree->root);
}
/* 树的层序遍历:背 */
int bnarySearchTreeOrder(BinarySearchTree *pTree)
{
    /* 判空 */
    if (pTree == NULL)
    {
        return NULL_PTR;
    }

    if (pTree->root == NULL)
    {
        return ON_SUCCESS;
    }

    DoubleLinkListQueue *queue = NULL;
    doubleLinkListQueueInit(&queue);

    //根结点入队
    doubleLinkListQueuePush(queue, pTree->root);

    //判断队列是不是空队列
    BinarySearchTreeNode *frontVal = NULL;
    while (!doubleLinkListQueueIsEmpty(queue))
    {
        //取出对头元素
        doubleLinkListQueueFront(queue, &frontVal);
        doubleLinkListQueuePop(queue);

        //打印器
        pTree->printFunc(frontVal->data);

        //左子树入队
        if (frontVal->left != NULL)
        {
            doubleLinkListQueuePush(queue, frontVal->left);
        }

        //右子树入队
        if (frontVal->right != NULL)
        {
            doubleLinkListQueuePush(queue, frontVal->right);
        }
    }

    //释放队列
    doubleLinkListQueueDestroy(queue);
    return ON_SUCCESS;
}

/* 树的高度 */
int bnarySearchTreeGetheight(BinarySearchTree *pTree, int *pHeight)
{
    //判空
    if (pTree == NULL || pHeight == NULL)
    {
        return NULL_PTR;
    }

    if (pTree->root == NULL)
    {
        //解引用
        *pHeight = 0;
        return ON_SUCCESS;
    }

    //程序到这个地方，根节点一定不NULL，一定有结点
    int height = 0;
    DoubleLinkListQueue *queue = NULL;
    doubleLinkListQueueInit(&queue);

    doubleLinkListQueuePush(queue, pTree->root);
    int levelSize = 1;

    //判断队列是不是空队列
    BinarySearchTreeNode *frontVal = NULL;
    while (!doubleLinkListQueueIsEmpty(queue))
    {
        //取出对头元素
        doubleLinkListQueueFront(queue, (void **)&frontVal);
        //出队
        doubleLinkListQueuePop(queue);

        //打印器
        pTree->printFunc(frontVal->data);

        levelSize--;

        //左子树入队
        if (frontVal->left != NULL)
        {
            doubleLinkListQueuePush(queue, frontVal->left);
        }

        //右子树入队
        if (frontVal->right != NULL)
        {
            doubleLinkListQueuePush(queue, frontVal->right);
        }

        /* 树的当前层结点遍历结束 */
        if (levelSize == 0)
        {
            height++;
            doubleLinkListQueueGetSize(queue, &levelSize);
        }
    }
    //释放队列
    doubleLinkListQueueDestroy(queue);
    return ON_SUCCESS;

}


/* 销毁；防止内存泄漏 */
int bnarySearchTreeDestroy(BinarySearchTree *pTree)
{
    #if 1
     /* 判空 */
    if (pTree == NULL)
    {
        return NULL_PTR;
    }

    if (pTree->root == NULL)
    {
        return ON_SUCCESS;
    }

    DoubleLinkListQueue *queue = NULL;
    doubleLinkListQueueInit(&queue);

    //根结点入队
    doubleLinkListQueuePush(queue, pTree->root);

    //判断队列是不是空队列
    BinarySearchTreeNode *frontVal = NULL;
    while (!doubleLinkListQueueIsEmpty(queue))
    {
        //取出对头元素
        doubleLinkListQueueFront(queue, &frontVal);
        doubleLinkListQueuePop(queue);

        // // 释放结点---打印器
        // pTree->printFunc(frontVal->data);不可在这里，下面还要用

        //左子树入队
        if (frontVal->left != NULL)
        {
            doubleLinkListQueuePush(queue, frontVal->left);
        }

        //右子树入队
        if (frontVal->right != NULL)
        {
            doubleLinkListQueuePush(queue, frontVal->right);
        }

        //释放结点
        if (frontVal != NULL)
        {
           free(frontVal);
           frontVal = NULL;
        }
    }

    //释放队列
    doubleLinkListQueueDestroy(queue);
    //释放树
    if(pTree  != NULL)
    {
        free(pTree);
        pTree = NULL;
    }

    return ON_SUCCESS;


    #else
        /*使用中序遍历的方式释放所有的结点 */
    #endif

}


/* 树的删除 */
int bnarySearchTreeDelete(BinarySearchTree *pTree, ELEMENTTYPE data)
{
     /* 判空 */
    if (pTree == NULL)
    {
        return NULL_PTR;
    }

  

}


/* 树是否存在该元素值 */
int bnarySearchTreeIsContainVa(BinarySearchTree *pTree, ELEMENTTYPE data)
{
    /* 判空 */
    if (pTree == NULL)
    {
        return NULL_PTR;
    }

    /* 程序走到这个地方, 一定不是空树 */
    BinarySearchTreeNode *travelNode = pTree->root;

    //比较
    int cmp = 0;
    while(travelNode != NULL)
    {
        cmp = pTree->compareFunc(data, travelNode->data);
        if(cmp < 0)
        {
          travelNode  = travelNode ->left;

        }
        else if (cmp == 0)
        {
            return 1;//找到了

        }
        else if(cmp > 0)
        {
           travelNode  = travelNode ->right; 
        }
    }
    //退出循环说明不存在，没找到
    return 0;

}


